In today's information age, communication devices, such as computers and computer peripherals, are often internetworked over a communication network. A common networking model routes packets of information within the communication network using a networking protocol such as the Internet Protocol (IP) or other network layer protocol. Some networking protocols, such as IP, are considered to be “connectionless” networking protocols. In a connectionless networking protocol, each packet of information includes a network layer address, and each router forwards the packet of information based upon the network layer address according to a predetermined routing protocol such as the Open Shortest Path First (OSPF) protocol, the Routing Information Protocol (RIP), Hello, or other routing protocol.
Thus, each router makes an independent forwarding decision for the packet based upon the network layer address. Essentially, each router partitions the entire set of network layer addresses into a number of Forwarding Equivalence Classes (FECs), and each FEC is mapped to a particular outgoing path (or set of paths, in the case of multi-path routing) based upon the routing protocol. The router determines an FEC for each packet of information based upon the network layer address of the packet, and forwards the packet of information to the corresponding outgoing path (or set of paths).
Network layer routing requires each router to process each packet of information at the network layer. This is an expensive and time-consuming operation that limits the performance of some routers and even prevents certain devices that do not support the networking protocol from performing routing and other functions on the packets.
Label switching can be used to eliminate the network layer processing by certain devices in the communication network. Label switching enables a packet to be transported across a network domain (referred to hereinafter as an “autonomous system” or “AS”) using labels rather than the network layer address. Specifically, a Label Switched Path (LSP) is established from an ingress point border device to an egress point border device in the AS. The LSP traverses a number of label switching devices. Each label switching device assigns a short, fixed-length value (i.e., a “label”) to each FEC that is supports. When the packet enters the ingress point border device, the ingress point border device uses the network address to assign the packet to a particular FEC, and inserts the corresponding label into the packet, specifically within a packet header. Each subsequent label switching device along the LSP uses the label in the packet to determine the next hop FEC for the packet, and replaces the label in the packet with a new label corresponding to the next hop FEC for the packet. The egress point border device removes the label from the packet. Thus, only the ingress point border device processes the packet at the network layer, and subsequent devices process the packet based upon the label only.
The Internet Engineering Task Force (IETF) Multi-Protocol Label Switching (MPLS) working group has defined an MPLS architecture for utilizing label switching for internetworking. MPLS is considered to be “multi-protocol” because it can be used with any network layer protocol, and is not limited to IP. An MPLS framework is described in an IETF Internet Draft document entitled A FRAMEWORK FOR MULTIPROTOCOL LABEL SWITCHING, which is referenced as draft-ietf-mpls-framework-02.txt (November 1997), and is hereby incorporated by reference in its entirety. The MPLS architecture is described in an IETF Internet Draft document entitled MULTIPROTOCOL LABEL SWITCHING ARCHITECTURE, which is referenced as draft-ietf-mpls-arch-05.txt (April 1999), and is hereby incorporated by reference in its entirety.
In order to use label switching for internetworking, each label switching device must learn the labels that are used by its neighboring label switching device(s). Therefore, the IETF MPLS working group has defined a Label Distribution Protocol (LDP) for distributing labels between neighboring label switching devices. LDP is described in an IETF Internet Draft document entitled LDP SPECIFICATION, which is referenced as draft-ietf-mpls-ldp-04.txt (May 1999), and is hereby incorporated by reference in its entirety.
Each label switching device maintains a label information base (LIB) for mapping each FEC to a corresponding label. When the label switching device receives a packet including a label, the label switching device utilizes the LIB to map the received label to a next hop FEC and to retrieve a label for the next hop FEC. The label switching device then replaces the label in the packet with the label for the next hop FEC, and forwards the resulting packet to the corresponding outgoing path (or set of paths).
In certain situations, it is desirable to use label switching for routing packets across multiple autonomous systems. Two neighboring autonomous systems share a common border device such that, with respect to a particular routing path, the shared border device is the egress point for one AS and the ingress point for the other AS. For convenience, the AS from which the shared border device receives the packet is referred to as the “incoming” AS, while the AS to which the shared border device forwards the packet is referred to as the “outgoing” AS.
In order to use label switching across autonomous systems, a two-tiered labeling scheme is employed. The ingress point border device in each AS establishes an LSP to the corresponding egress point border device within the AS. Whenever an ingress point border device forwards a packet, the ingress point border device inserts two labels (referred to hereinafter as a “label stack”) into the packet, specifically within a packet header. One label (referred to hereinafter as a “border label”) is a label associated with the egress point border device within the AS, which the egress point border device provides to the ingress point border device along with “reachability” information using a modified Border Gateway Protocol (BGP). The other label (referred to hereinafter as an “interior label”) is a label associated with the next hop FEC for the packet, as described above. The location of the interior label within the packet header is the same whether or not the packet header includes a border label, and therefore intermediate devices process the packet in the same manner whether or not the packet header includes a border label. Within a particular AS, each interior (non-border) device processes the packet based upon the interior label, and replaces the interior label in the packet with a new interior label corresponding to the next hop FEC for the packet, as described above. The egress point border device removes the border label and the interior label from the packet. If the egress point border device is also an ingress point for a neighboring AS, then the ingress point border device inserts a new border label and a new interior label into the packet. The new border label is a label associated with an egress point border device within the neighboring AS, and the interior label is a label associated with the next hop FEC for the packet.
Although the two-tier mechanism allows label switching to be used for routing packets across multiple autonomous systems, the two-tier mechanism has a number of disadvantages. One disadvantage is that the two-tier mechanism requires that BGP be modified or extended to distribute labels. Another disadvantage is that the label stack adds a substantial amount of overhead per packet.
Thus, a mechanism for using label switching across autonomous systems that does not utilize a label stack and does not require any modifications to BGP would be valuable.